package org.example;

import java.util.*;

public class AppTest03 {

    // 路径总和1
    class Solution {
        public boolean hasPathSum(TreeNode root, int sum) {
            if (root == null) return false;
            // todo 左右为空才可以
            if (root.left == null && root.right == null) return root.val == sum;
            return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
        }
    }

    // 路径总和2
    class Solution {
        public boolean hasPathSum(TreeNode root, int sum) {
            if (root == null) return false;
            // todo 注意加入判空条件
            if (root.left == null && root.right == null) return root.val == sum;
            return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
        }
    }

    // 路径总和3
    class Solution {
        public boolean hasPathSum(TreeNode root, int sum) {
            if (root == null) return false;
            if (root.left == null && root.right == null) return sum == root.val;
            return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);

        }
    }

    // 杨辉三角1
    class Solution {
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> ret = new ArrayList<List<Integer>>();
            for (int i = 0; i < numRows; i++) {
                List<Integer> row = new ArrayList<Integer>();
                for (int j = 0; j <= i; j++) {
                    // todo 最左最右为1的情况
                    if (j == 0 || j == i) row.add(1);
                    else row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
                ret.add(row);
            }
            return ret;
        }
    }

    // 杨辉三角2
    class Solution {
        public List<List<Integer>> generate(int numRows) {
            // todo 应该是new对象
            List<List<Integer>> ret = new ArrayList<>();
            for (int i = 0; i < numRows; i++) {
                List<Integer> retInnter = new ArrayList<>();
                for (int j = 0; j <= i; j++) {
                    if (j == 0 || j == i) retInnter.add(1);
                    else {
                        retInnter.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                    }
                }
                ret.add(retInnter);
            }
            return ret;
        }
    }

    // 杨辉三角3
    class Solution {
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> ret = new ArrayList<>();
            for (int i = 0; i < numRows; i++) {
                List<Integer> inner = new ArrayList<>();
                for (int j = 0; j <= i; j++) {
                    if (j == 0 || j == i) inner.add(1);
                    else inner.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
                ret.add(inner);
            }
            return ret;
        }
    }

    // 杨辉三角第k行1
    class Solution {
        public List<Integer> getRow(int rowIndex) {
            // todo List是抽象类，不能实例化
            List<Integer> row = new ArrayList<>();
            row.add(1);
            for (int i = 1; i <= rowIndex; i++) {
                // todo 兼容长整型
                row.add((int) ((long) row.get(i - 1) * (rowIndex - i + 1) / i));
            }
            return row;
        }
    }

    // 杨辉三角第k行2
    class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> row = new ArrayList<>();
            row.add(1);
            for (int i = 1; i <= rowIndex; i++) {
                long nextLong = (long) row.get(i - 1) * (rowIndex - i + 1) / i;
                int nextInt = (int) nextLong;
                row.add(nextInt);
            }
            return row;
        }
    }

    // 杨辉三角第k行3
    class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> ret = new List<>();
            ret.add(1);
            for (int i = 1; i <= rowIndex; i++) {
                long next = (long) ret.get(i - 1) * (rowIndex - i + 1) / i;
                ret.add((int) next);
            }
            return ret;
        }
    }

    // 买股票的最佳时机
    class Solution {
        // 1
        public int maxProfit(int prices[]) {
            int indexLowest = 0;
            int bestProfit = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] < prices[indexLowest]) indexLowest = i;
                else {
                    int curProfit = prices[i] - prices[indexLowest];
                    bestProfit = Math.max(curProfit, bestProfit);
                }
            }
            return bestProfit;
        }

        // 2
        public int maxProfit(int prices[]) {
            int mostProfit = 0;
            int lowestPrice = prices[0];
            for (int price : prices) {
                if (price < lowestPrice) {
                    lowestPrice = price;
                } else {
                    int curProfit = price - lowestPrice;
                    mostProfit = Math.max(mostProfit, curProfit);
                }
            }
            return mostProfit;
        }

        // 3
        public int maxProfit(int prices[]) {
            int lowestPrice = prices[0];
            int maxProf = 0;
            for (int price : prices) {
                if (price < lowestPrice) lowestPrice = price;
                else {
                    int curProf = price - lowestPrice;
                    maxProf = Math.max(curProf, maxProf);
                }
            }
            return maxProf;
        }
    }

    // 多次买卖股票最大收益
    class Solution {
        // 1
        public int maxProfit(int[] prices) {
            int ans = 0;
            int n = prices.length;
            for (int i = 1; i < n; i++) {
                ans += Math.max(0, prices[i] - prices[i - 1]);
            }
            return ans;
        }

        // 2
        public int maxProfit(int[] prices) {
            int prof = 0;
            if (prices.length < 2) return 0;
            for (int i = 1; i < prices.length; i++) {
                int diff = prices[i] - prices[i - 1];
                if (diff > 0) {
                    prof += diff;
                }
            }
            return prof;
        }

        // 3
        public int maxProfit(int[] prices) {
            int profit = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] - prices[i - 1] > 0) {
                    profit += prices[i] - prices[i - 1];
                }
            }
            return profit;
        }
    }

    // 验证回文字符串
    class Solution {
        //1
        public boolean isPalindrome(String s) {
            int n = s.length();
            int left = 0, right = n - 1;
            while (left < right) {
                // todo 不能把boolean存起来
//                boolean leftValid = Character.isLetterOrDigit(s.charAt(left)),
//                        rightValid = Character.isLetterOrDigit(s.charAt(right));
//                while (left < right && !leftValid) left++;
//                while (left < right && !rightValid) right--;
                while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
                while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
                if (left < right) {
                    // todo 忽略大小写
                    if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                        return false;
                    }
                    // todo 自增自减
                    left++;
                    right--;
                }
            }
            return true;
        }

        //2
        public boolean isPalindrome(String s) {
            int left = 0;
            int right = s.length() - 1;
            while (left < right) {
                while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
                while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
                if (left < right && Character.toLowerCase(s.charAt(left)) !=
                        Character.toLowerCase(s.charAt(right))) return false;
                left++;
                right--;
            }
            return true;
        }

        //3
        public boolean isPalindrome(String s) {
            int left = 0;
            int right = s.length() - 1;
            while (left < right) {
                while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
                while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
                if (left < right && Character.toLowerCase(s.charAt(left)) !=
                        Character.toLowerCase(s.charAt(right))) return false;
                left++;
                right--;
            }
            return true;
        }
    }

    // 只出现一次的数字
    class Solution {
        // 1
        public int singleNumber(int[] nums) {
            int res = 0;
            for (int num : nums) {
                res ^= num;
            }
            return res;
        }

        // 2
        public int singleNumber(int[] nums) {
            int res = 0;
            for (int num : nums) res ^= num;
            return res;
        }

        // 3
        public int singleNumber(int[] nums) {
            int res = 0;
            for (int num : nums) {
                res ^= num;
            }
            return res;
        }
    }

    // 链表是否有环
    class Solution{
        // 1
        public boolean hasCycle(ListNode head) {
            if (head == null || head.next == null) return false;
            ListNode slow = head;
            ListNode fast = head.next;
            while (slow != fast) {
                if (fast == null || fast.next == null) return false;
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }

        // 2
        public boolean hasCycle(ListNode head) {
            if (head == null || head.next == null) return false;
            ListNode slow = head, fast = head.next;
            while (slow != fast) {
                if (fast.next == null || fast.next.next == null) return false;
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }

        // 3
        public boolean hasCycle(ListNode head) {
            if (head == null || head.next == null) return false;
            ListNode slow = head;
            ListNode fast = head.next;
            while (slow != fast) {
                if (fast.next == null || fast.next.next == null) return false;
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }
    }

    // 最小栈1
    class MinStack{
        LinkedList<Integer> xStack;
        LinkedList<Integer> minStack;

        public MinStack() {
            xStack = new LinkedList<>();
            minStack = new LinkedList<>();
            minStack.push(Integer.MAX_VALUE);
        }

        public void push (int x) {
            xStack.push(x);
            minStack.push(Math.min(minStack.peek(), x));
        }

        public void pop () {
            xStack.pop();
            minStack.pop();
        }

        public int top() {
            return  xStack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }
    // 最小栈2
    class MinStack{

        LinkedList<Integer> valueStack;
        LinkedList<Integer> minimumStack;

        public MinStack() {
            valueStack = new LinkedList<>();
            minimumStack = new LinkedList<>();
            minimumStack.push(Integer.MAX_VALUE);
        }

        public void push (int x) {
            valueStack.push(x);
            minimumStack.push(Math.min(x, minimumStack.peek()));
        }

        public void pop () {
            valueStack.pop();
            minimumStack.pop();
        }

        public int top() {
            return valueStack.peek();
        }

        public int getMin() {
            return minimumStack.peek();
        }
    }
    // 最小栈3
    class MinStack{
        LinkedList<Integer> valueStack;
        LinkedList<Integer> minimumStack;

        public MinStack() {
            valueStack = new LinkedList<>();
            minimumStack = new LinkedList<>();
            minimumStack.push(Integer.MAX_VALUE);
        }

        public void push (int x) {
            valueStack.push(x);
            minimumStack.push(Math.min(x, minimumStack.peek()));
        }

        public void pop () {
            valueStack.pop();
            minimumStack.pop();
        }

        public int top() {
            return valueStack.peek();
        }

        public int getMin() {
            return minimumStack.peek();
        }
    }

    // 相交链表
    class Solution {
        //1
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;
            // todo 不能操作原指针，要复制一份出来
            ListNode aPointer = headA, bPointer=headB;
            while (aPointer != bPointer) {
                // todo 指针指向null为止，不相交则最终a、b指针都是null，跳出循环
                aPointer = (aPointer == null ? headB : aPointer.next);
                bPointer = (bPointer == null ? headA : bPointer.next);
            }
            return aPointer;
        }
        //2
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;
            ListNode aPointer = headA, bPointer=headB;
            while (aPointer != bPointer) {
                aPointer = (aPointer == null ? headB : aPointer.next);
                bPointer = (bPointer == null ? headA : bPointer.next);
            }
            return aPointer;
        }
        //3
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;
            ListNode pointerA = headA, pointerB = headB;
            while (pointerA != pointerB) {
                pointerA = pointerA == null ? headB : pointerA.next;
                pointerB = pointerB == null ? headA : pointerB.next;
            }
            return pointerA;
        }
    }

    // 有序数组两数之和
    class Solution {
        //1
        public int[] twoSum(int[] numbers, int target) {
            int low = 0, high = numbers.length - 1;
            while (low < high) {
                int sum = numbers[low] + numbers[high];
                if (sum == target) return new int[] {low + 1, high + 1};
                else if (sum < target) low++;
                else high--;
            }
            return new int[]{-1, -1};
        }
        //2
        public int[] twoSum(int[] numbers, int target) {
            int head = 0, tail = numbers.length - 1;
            while (head < tail) {
                int sum = numbers[head] + numbers[tail];
                if (sum == target) return new int[]{head + 1, tail + 1};
                else if (sum < target) head++;
                else tail--;
            }
            return new int[] {-1, -1};
        }
        //3
        public int[] twoSum(int[] numbers, int target) {
            int head = 0, tail = numbers.length -1;
            while (head < tail) {
                int sum = numbers[head] + numbers[tail];
                if (sum == target) return new int[] {head, tail};
                else if (sum < target) head++;
                else tail--;
            }
            return new int[] {-1, -1};
        }

    }

    // 多数元素1
    class Solution {
        public int majorityElement(int[] nums) {
            Map<Integer, Integer> counts = countNums(nums);
            // todo 利用majorityEntry变量
            Map.Entry<Integer, Integer> majorityEntry = null;
            // todo 用entrySet()方法
            for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
                if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                    majorityEntry = entry;
                }
            }
            // todo 是getKey()
            return majorityEntry.getKey();
        }

        private Map<Integer, Integer> countNums(int[] nums) {
            Map<Integer, Integer> counts = new HashMap<>();
            for (int num : nums) {
                if (!counts.containsKey(num)) counts.put(num, 1);
                else counts.put(num, counts.get(num) + 1);
            }
            return counts;
        }
    }
    // 多数元素2
    class Solution {
        public int majorityElement(int[] nums) {
            Map<Integer, Integer> countsMap = getCounts(nums);
            Map.Entry<Integer, Integer> majorityEntry = null;
            for (Map.Entry<Integer, Integer> entry : countsMap.entrySet()) {
                if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                    majorityEntry = entry;
                }
            }
            return majorityEntry.getKey();
        }

        private Map<Integer, Integer> getCounts(int[] nums) {
            Map<Integer, Integer> countsMap = new HashMap<>();
            for (int num : nums) {
                if (!countsMap.containsKey(num)) {
                    countsMap.put(num, 1);
                }
                else {
                    countsMap.put(num, countsMap.get(num) + 1);
                }
            }
            return countsMap;
        }
    }
    // 多数元素3
    class Solution {
        public int majorityElement(int[] nums) {
            Map<Integer, Integer> entries = getEntries(nums);
            Map.Entry<Integer, Integer> majorityEntry = null;
            for (Map.Entry<Integer, Integer> entry : entries.entrySet()) {
                if (majorityEntry == null || majorityEntry.getValue() < entry.getValue()) {
                    majorityEntry = entry;
                }
            }
            return majorityEntry.getKey();
        }

        private Map<Integer, Integer> getEntries(int[] nums) {
            Map<Integer, Integer> entries = new HashMap<>();
            for (int num : nums) {
                if (!entries.containsKey(num)) entries.put(num, 1);
                else entries.put(num, entries.get(num) + 1);
            }
            return entries;
        }

    }

    // 阶乘后的零
    class Solution {
        //1
        public int trailingZeroes(int n) {
            int zeroCount = 0;
            long currentMultiple = 5;
            while (n >= currentMultiple) {
                zeroCount += (n / currentMultiple);
                currentMultiple *= 5;
            }
            return zeroCount;
        }

        //2
        public int trailingZeroes(int n) {
            long multiple = 5;
            int zeroes = 0;
            while (n >= multiple) {
                zeroes += n / multiple;
                multiple *= 5;
            }
            return zeroes;
        }

        //3
        public int trailingZeroes(int n) {
            long multiple = 5;
            int zeroes = 0;
            while (n <= multiple) {
                zeroes += n / multiple;
                multiple *= 5;
            }
            return zeroes;
        }
    }
}



















